package com.fe.class02;

import java.util.*;

/**
 * @Description 一个数组中只有一种数出现K次，其他数都出现了M次，
 * M > 1, K < M，找到出现了K次的数， 要求，额外空间复杂度O(1)，时间复杂度O(N)
 * @Author sosuke :-)
 * @Date 2021/12/3 06:40
 */
public class Code05_KM_EvenTimesOddTimes {

    public static int onlyKTimesNum(int[] arr, int m) {
        /**
         * 1. int类型是32位，将int数组arr中的每个数的二进制位按位进行累加，得到一个32位的数组t[]，
         *       t[i]代表arr数组所有元素的二进制位第i位的累加和
         */
        int[] t = new int[32];
        // 这两个for循环时间复杂度为O(n)，因为内层的循环次数是固定的32
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                t[i] += (num >> i) & 1; // 获取num的第i位
            }
        }

        /**
         * 2. 第i位数组元素的值t[i] = x*k + y*m，(x=0或1，y >=0)，即第i位的值由以下内容组成：
         * 如果出现了K次的数的第i位二进制位为1，则包含1*k；
         * 如果出现了M次的数中有y种数的第i位二进制为1，则包含y*m；
         * 所以：如果t[i] % m == 0，表示x=0，即出现了K次的数的第i位二进制位为0；
         *      如果t[i] % m != 0，表示x=1，即出现了K次的数的第i位二进制位为1；
         */
        int kTimesNum = 0; // 表示出现了k次的数，初始值设置位0，表示所有二进制位都为0，方便后续设置特定位置的二进制位
        for (int i = 0; i < 32; i++) {
            if (t[i] % m != 0) { // 表示kTimesNum的第i位为1
                kTimesNum |= (1 << i); // 设置kTimesNum的第i位为1
            }
        }

        return kTimesNum;
    }

    public static void main(String[] args) {
        int testTimes = 10000; // 测试次数
        int maxKinds = 4; // 数组中最多有几种数
        int maxValue = 100; // 数组元素最大值
        int max = 9;
        boolean successed = true;
        for (int i = 0; i < testTimes; i++) {
            // 生成满足条件的k，m
            int a = (int) (Math.random() * max) + 1; // [1,9]
            int b = (int) (Math.random() * max) + 1; // [1,9]
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            if (k == m) {
                m++; // 保证 k<m, m>1
            }
            // 生成满足条件的数组
            int[] arr = generateRandomArray(maxKinds, maxValue, k, m);
            int res1 = onlyKTimesNum(arr, m);
            int res2 = testForKTimesNum(arr, k, m);
            if (res1 != res2) {
                successed = false;
                System.out.println(Arrays.toString(arr));
                System.out.println("res1 = " + res1 + ", res2 = " + res2);
            }
        }
        System.out.println(successed ? "Nice" : "Fuck");
        // 生成满足条件的数组
        // 生成满足条件的k，m
        int a = (int) (Math.random() * max) + 1; // [1,9]
        int b = (int) (Math.random() * max) + 1; // [1,9]
        int k = Math.min(a, b);
        int m = Math.max(a, b);
        int[] arr = generateRandomArray(maxKinds, maxValue, k, m);
        System.out.println("k = " + k + ", m=" + m);
        System.out.println("arr = " + Arrays.toString(arr));
        System.out.println("res1 = " + onlyKTimesNum(arr, m) + ", res2 = " + testForKTimesNum(arr, k, m));
    }

    /**
     * arr数组中只有一种数出现K次，其他的数都出现了M次
     *
     * @param maxKinds
     * @param maxValue
     * @param k
     * @param m
     * @return
     */
    private static int[] generateRandomArray(int maxKinds, int maxValue, int k, int m) {
        // 有多少种数
        // [0,maxKinds-1) + 2 = [2,maxKinds+1) = [2,maxKinds]
        int numKinds = (int) ((Math.random() * (maxKinds - 1)) + 2);
        int[] arr = new int[k + (numKinds - 1) * m]; // 定义数组，数组长度是计算的

        // 依次填充k次的一种数，和m次的其他数
        // 出现k次的数
        int kTimesNum = randomNum(maxValue);
        int index = 0;
        // 填充出现k次的数
        for (; index < k; index++) {
            arr[index] = kTimesNum;
        }
        numKinds--;
        Set<Integer> set = new HashSet<>();
        set.add(kTimesNum);
        // 填充出现m次的数
        for (int i = 0; i < numKinds; i++) {
            int curNum = 0;
            do {
                curNum = randomNum(maxValue);
            } while (set.contains(curNum)); // 不能和之前生成的数相同
            set.add(curNum); // 把生成的数放到set中，防重
            for (int j = 0; j < m; j++) {
                arr[index++] = curNum;
            }
        }
        // arr到这里就算填充完毕
        for (int i = 0; i < arr.length; i++) {
            int j = (int) (Math.random() * arr.length);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        return arr;
    }

    // [-maxValue, +maxValue]
    private static int randomNum(int maxValue) {
        // [0,maxValue] - [0,maxValue] = [-maxValue, +maxValue]
        return (int) ((Math.random() * (maxValue + 1))) - (int) ((Math.random() * (maxValue + 1)));
    }

    /**
     * arr数组中只有一种数出现K次，其他的数都出现了M次
     * 使用HashMap统计词频
     *
     * @param arr
     * @param k   k<m
     * @param m   m>1
     * @return 返回出现了k次的数
     */
    public static int testForKTimesNum(int[] arr, int k, int m) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }
}
